package algorithm.t202112;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/17 16:23
 * @description :1道
 * 今天总体还行，学习了邻接矩阵和folyd算法，算是对图论进行了一点点学习，明天去学一学邻接表和其他图的知识，还得要慢慢复习。刚才期末考试时间出来了，12月
 24号早上8.30考人工智能，还有就是今早给酷渲人事说了我可能22号来不了的消息，到现在也没有回文，不知道什么情况，有点害怕，如果这个公司不要我，那我就亏大了，
 现在要是重新找需要花费时间和精力，而且我的房子已经租了，耽误不起啊，艹，一想到这里就生气，学校这边对于我们的实习什么一直处于一直不太支持的样子，很烦！
 还有就是这突然的西安疫情，唉，烦，还有毕业论文，毕业实习这些事情等着做，和兄弟们华山也没有爬，好了好了，先把目光专注于实习这块，还有就是不变的：提升自己。
 春招冲大厂！干
 persevere to last
 2021.12.17
 李红磊
 2021年12月17日21:02:40
 */
public class t20211217 {

    int[][] path = new int[6][6];

    private void getPath(int i, int j) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        if (path[i][j] == 0) {//表示两点是直接连的，没有中间节点
            System.out.println(i + "  " + j);
        } else {
            getPath(i, path[i][j]);
            getPath(path[i][j], j);
        }

    }


    public void tes() {
        final int INF = 0x3f3f3f3f;
        int[][] points = new int[][]{
                {1, 2, 20},
                {2, 4, 15},
                {2, 3, 15},
                {1, 5, 30},
                {3, 5, 10}
        };
        int[][] dis = new int[6][6];
        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis[0].length; j++) {
                if (i != j) dis[i][j] = INF;
            }
        }

        for (int[] p : points) {
            int i = p[0], j = p[1], w = p[2];
            dis[i][j] = w;
        }

        //佛洛依德
        for (int k = 1; k <= 5; k++) {
            for (int i = 1; i <= 5; i++) {
                if (dis[i][k] == INF) continue;
                for (int j = 1; j <= 5; j++) {
                    if (dis[i][j] > dis[i][k] + dis[k][j]) {
                        dis[i][j] = dis[i][k] + dis[k][j];
                        this.path[i][j] = k;//记录中间节点
                    }
                }
            }
        }

        /*for (int[] row : dis) {
            for (int item : row) {
                System.out.print(item == INF ? -1 + "\t" : item + "\t");
            }
            System.out.println();
        }*/


    }

    public int networkDelayTime(int[][] times, int n, int k) {
        final int INF = 0x3f3f3f3f;

        //使用邻接矩阵存图
        int[][] d = new int[n + 1][n + 1];

        //初始化邻接矩阵
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d[0].length; j++) {
                if (i != j) d[i][j] = INF;
            }
        }

        for (int[] t : times) {
            int i = t[0], j = t[1], w = t[2];
            d[i][j] = w;
        }

        //floyd
        //求最短路径
        for (int m = 1; m <= n; m++) {
            for (int i = 1; i <= n; i++) {
                if (d[i][m] == INF) continue;
                for (int j = 1; j <= n; j++) {
                    d[i][j] = Math.min(d[i][j], d[i][m] + d[m][j]);
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i < d[k].length; i++) {
            if (d[k][i] == INF) return -1;
            ans = Math.max(ans, d[k][i]);
        }
        return ans;
    }

    //1518.换酒问题
    public int numWaterBottles(int numBottles, int numExchange) {
        int ans = numBottles;
        int cur = numBottles;
        while (cur / numExchange != 0) {
            int tem = cur / numExchange;
            ans += tem;
            cur /= numExchange;
        }

        return ans;
    }

    public static void main(String[] args) {
        t20211217 t20211217 = new t20211217();
        System.out.println(t20211217.numWaterBottles(9, 3));


    }


}
